/*
写出一个算法确定一个有n个顶点e条边的有向图是否包含回路，
所设计的算法的时间复杂度应该是O(n + e)。
*/

#include "ADJ_List.h"
#include "iostream"
#include <stack>
using namespace std;

/*****核心功能函数*****/
bool HasCirclePath(Graph_ADJ_List &g)
{
    using std::stack;
    stack<int> s;
    for (int i = 0; i < g.numV; i++)
    {
        if (!g.in_degree[i]) //图中度数为0的结点入栈
        {
            s.push(i);
        }
    }
    int count = 0;
    while (!s.empty())
    {
        int v = s.top();
        s.pop();
        count++;
        g.mark[v] = 1;
        for (Edge e = g.firstE(v); g.isE(e); e = g.nextE(e))
        {
            g.in_degree[e.to]--;
            if (!g.in_degree[e.to])
            {
                s.push(e.to);
            }
        }
    }

    return (count < g.numV);
}
/*****核心功能函数*****/

/*****主函数*****/
int main()
{

    Graph_ADJ_List *g1 = new Graph_ADJ_List(1);
    cout << "g1中";
    if (HasCirclePath(*g1))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g2 = new Graph_ADJ_List(5);
    g2->setE(0, 1, 0);
    g2->setE(1, 2, 0);
    g2->setE(2, 4, 0);
    g2->setE(4, 3, 0);
    g2->setE(3, 1, 0);
    cout << "g2中";
    if (HasCirclePath(*g2))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g3 = new Graph_ADJ_List(5);
    cout << "g3中";
    if (HasCirclePath(*g3))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g4 = new Graph_ADJ_List(5);
    g4->setE(0, 1, 0);
    g4->setE(1, 2, 0);
    g4->setE(1, 3, 0);
    g4->setE(2, 4, 0);
    g4->setE(3, 4, 0);
    cout << "g4中";
    if (HasCirclePath(*g4))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g5 = new Graph_ADJ_List(5);
    g5->setE(0, 0, 0);
    g5->setE(1, 2, 0);
    g5->setE(1, 3, 0);
    g5->setE(2, 4, 0);
    g5->setE(3, 4, 0);
    cout << "g5中";
    if (HasCirclePath(*g5))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g6 = new Graph_ADJ_List(5);
    g6->setE(0, 1, 0);
    g6->setE(1, 2, 0);
    g6->setE(2, 3, 0);
    g6->setE(3, 2, 0);
    g6->setE(2, 4, 0);
    cout << "g6中";
    if (HasCirclePath(*g6))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g7 = new Graph_ADJ_List(5);
    g7->setE(1, 2, 0);
    g7->setE(2, 4, 0);
    g7->setE(4, 3, 0);
    g7->setE(3, 1, 0);
    cout << "g7中";
    if (HasCirclePath(*g7))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    system("pause");
}
/*****主函数*****/